#
# @lc app=leetcode.cn id=338 lang=python
#
# [338] 比特位计数
#

# @lc code=start
class Solution(object):
    def countBits(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        result=[0]
        for i in range(1,n+1):
            # result.append(bin(i).count('1'))
            # 优化，使用移位操作,偶数是乘2，相当于左移一位，所以1的数量不变，
            # 奇数是加1，相当于右移一位，所以1的数量增加1
            if i%2==0:
                result.append(result[i//2])
            else:
                result.append(result[i-1]+1)
        return result


# @lc code=end

